/**
 * @param {number[][]} graph
 * @return {boolean}
 */
 var isBipartite = function (graph) {
  // 深搜
  function dfs(index) {
    // 遍历并查看index与i节点的关系
    for (let i = 0; i < graph[index].length; i++) {

      if (type[graph[index][i]] == type[index]) { // 如果他们两者的type一样，也就是在同一个阵营，但是一条边是不能两个节点都是同一个阵营的，因此返回false
        return false;
      } else if (type[graph[index][i]] == 0) { // 如果说i这个节点没有加入过阵营，则需设置为与index不同的阵营
        type[graph[index][i]] = type[index] == 1 ? 2 : 1;
        if (!dfs(graph[index][i], graph))
          return false;
      }
    }
    // 除了以上的情况，其实说明这两个节点就是可以存在于不同的阵营了
    return true;
  }
  // type表示类型，一开始大家都是0，根据type的不同区分阵营
  // type为1的为一个阵营
  // type为2的为一个阵营
  let type = new Array(graph.length).fill(0);
  for (let i = 0; i < graph.length; i++) {
    // 如果type为0，表示没有加入过任何阵营
    if (type[i] == 0) {
      // 先加入1的阵营
      type[i] = 1;
      if (!dfs(i))
        return false;
    }
  }
  return true;
};

let graph = [[1,2,3],[0,2],[0,1,3],[0,2]];
console.log(isBipartite(graph));
graph = [[1,3],[0,2],[1,3],[0,2]];
console.log(isBipartite(graph));
